package dp;

public class _06_343_整数拆分 {

    public static int integerBreak(int n) {
    	int N = 60;
    	int dp[] = new int[N];
    	dp[1] = 0;
    	dp[2] = 1;
    	for(int i = 2; i <= n; i++) {
    		for(int j = 1; j < i; j++) {
    			/* 
    			 * j*(i-j)是把i拆分成了两个数进行计算
    			 * j*dp[i-j]是把i拆分成了j和dp[x]个数进行计算，这个x是前面已经计算过的dp值
    			 * 比如n=10，假设通过递推会把dp[5]的最大值得到，
    			 * 5的值已经是乘积最大值，那么j*dp[5]就是拆分成：j乘以->和是5且构成乘积的最大值
    			 * 这里的dp[5]已经是经过多个数乘积最大值得来的，所以j*dp[5]相当于j*多个数字
    			 */
    			dp[i] = Math.max(dp[i], j*(i-j));
    			dp[i] = Math.max(dp[i], j*dp[i-j]);
    		}
    	}
    	
    	return dp[n];
    }
    
    public static void main(String[] args) {
		System.out.println(integerBreak(10));
	}
}
